package com.leetcode.algorithm.y22.m06;

/**
 * 1588. 所有奇数长度子数组的和
 * 
 * https://leetcode.cn/problems/sum-of-all-odd-length-subarrays/
 * 
 * @author jie.deng
 *
 */
public class Question1588Solution01 {

	public int sumOddLengthSubarrays(int[] arr) {
		// 求前缀和
		int len = arr.length;
		int[] prefixSumArr = new int[len];
		prefixSumArr[0] = arr[0];
		for (int i = 1; i < prefixSumArr.length; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];
		}

		int sum = 0;
		for (int i = 1; i <= prefixSumArr.length; i = i + 2) {
			for (int j = i - 1; j < len; j++) {
				sum += prefixSumArr[j];
			}
			for (int j = 0; j < len - i; j++) {
				sum -= prefixSumArr[j];
			}
		}

		return sum;
	}

}
